package LeetCode;

import java.util.Arrays;

public class LC_475_Heaters {

    public static void main(String[] args) {

    }

    class Solution {

        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int left = 0, right = heaters.length - 1;
            int[] lefts = new int[houses.length];
            int[] rights = new int[houses.length];
            for (int i = 0; i < houses.length; i++) {
                while (left < heaters.length && heaters[left] <= houses[i]) {
                    lefts[i] = left + 1;
                    left++;
                }
                left = lefts[i] != 0 ? (lefts[i] - 1) : 0;
                while (right >= left && heaters[right] >= houses[i]) {
                    rights[i] = right + 1;
                    right--;
                }
                right = heaters.length - 1;
            }
            int ret = 0;
            for (int i = 0; i < houses.length; i++) {
                int min = Integer.MAX_VALUE;
                if (lefts[i] != 0) min = Math.min(houses[i] - heaters[lefts[i] - 1], min);
                if (rights[i] != 0) min = Math.min(heaters[rights[i] - 1] - houses[i], min);
                ret = Math.max(min, ret);
            }

            System.out.println(ret);
            return ret;
        }

    }
}